package com.xdja.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Average {
    public static void main(String[] args) {
        Integer[] source = new Integer[]{1, 2, 3, 4, 5, null, 6};
//        Integer[] source = new Integer[]{1, 2, 3, 4, 5, null, 6,7,9,11,23,75,36,77,69};
        TreeNode root = new TreeNode(source[0]);
        buildTree(root, source, 0);
//        printTree(root);
        List<Float> result = new ArrayList<>();
        traverseTree(result, root);
        System.out.println();
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i));
            if (i != result.size() - 1) {
                System.out.print(",");
            }
        }
    }

    private static void traverseTree(List<Float> result, TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            float sum = 0;//记录每一层数值之和
            long count = 0;//记录每一层node个数
            Queue<TreeNode> temp = new LinkedList<>();
            while (!queue.isEmpty()) {
                TreeNode n = queue.poll();
                count++;
                sum += n.data;
                printNode(n);
                if (n.left != null) {
                    temp.add(n.left);
                }
                if (n.right != null) {
                    temp.add(n.right);
                }
            }
            //下一层级赋值，继续解析下一层节点
            queue = temp;
            result.add(sum / count);
        }
    }

    private static void printTree(TreeNode root) {
        if (root == null) {
            return;
        }
        printNode(root);
        System.out.println();
        printTree(root.left);
        printTree(root.right);
    }

    private static void printNode(TreeNode node) {
        System.out.print(node.data);
    }

    private static void buildTree(TreeNode treeNode, Integer[] source, int index) {
        //左叶子节点的索引
        int leftIndex = (index + 1) * 2 - 1;
        //右叶子节点的索引
        int rightIndex = leftIndex + 1;
//        treeNode.data = source[index];
        if (leftIndex < source.length && source[leftIndex] != null) {
            treeNode.left = new TreeNode(source[leftIndex]);
            buildTree(treeNode.left, source, leftIndex);
        }
        if (rightIndex < source.length && source[rightIndex] != null) {
            treeNode.right = new TreeNode(source[rightIndex]);
            buildTree(treeNode.right, source, rightIndex);
        }
    }

    private static class TreeNode {
        public TreeNode(int data) {
            this.data = data;
        }

        private int data;
        private TreeNode left;
        private TreeNode right;
    }
}

